import java.util.Stack;

/**
 * @author VernHe
 * @date 2021年05月18日 15:02
 */
public class Solution_084 {
    public static void main(String[] args) {
        System.out.println(new Solution_084().largestRectangleArea1(
//                new int[]{2, 1, 5, 6, 2, 3}
//                new int[]{2, 1, 2}
                new int[]{5, 4, 1, 2}
//                new int[]{4, 2, 0, 3, 2, 5}
//                new int[]{3, 6, 5 ,7 ,4 ,8, 1, 0}
        ));
    }

    // 单调递增栈
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        // 参数判断
        if (heights == null || heights.length == 0) {
            return res;
        }
        for (int height : heights) {
            System.out.printf(height + " ");
        }
        System.out.println();
        // 定义变量
        // 单调递增栈，用于保存高度
        Stack<Integer> stack = new Stack();
        // 初始化
        // 先入栈一个
        stack.add(0);

        // 循环，入栈
        for (int i = 1; i < heights.length; i++) {
            // 如果是递增的
            if (!stack.isEmpty() && heights[i] >= heights[stack.peek()]) {
                stack.add(i);
                System.out.println(heights[i] + "入栈");
            } else {
                if (stack.isEmpty()) {
                    System.out.println("栈空了，" + heights[i] + "直接入栈");
                    stack.add(i);
                    continue;
                }
                // 出栈，计算最大面积
                int topIndex = stack.pop();
                System.out.println(heights[topIndex] + "出栈了");
                int width = i - topIndex;
                int pre = topIndex - 1;
                while (pre >= 0 && heights[pre] >= heights[topIndex]) {
                    pre--;
                    width++;
                }
                int newValue = heights[topIndex] * width;
                System.out.println(heights[topIndex] + "---" + width);
                res = Math.max(res, newValue);
                i--;
            }
            System.out.println(stack);
            System.out.println("--------------");
        }

        System.out.println("开始一直出栈：");
        while (!stack.isEmpty()) {
            int topIndex = stack.pop();
            int width = heights.length - topIndex;
            int pre = topIndex - 1;
            while (pre >= 0 && heights[pre] >= heights[topIndex]) {
                pre--;
                width++;
            }
            System.out.println(heights[topIndex] + "---" + width);
            res = Math.max(res, heights[topIndex] * width);
        }
        return res;
    }

    public int largestRectangleArea1(int[] heights) {
        int res = 0;
        // 参数判断
        if (heights == null || heights.length == 0) {
            return res;
        }
        // 在原有基础上两边补0
        int[] new_heights = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            new_heights[i + 1] = heights[i];
        }
        // 定义变量
        // 单调递增栈，用于保存高度
        Stack<Integer> stack = new Stack();
        // 初始化
        // 先入栈一个
        stack.add(0);
        for (int i = 1; i < new_heights.length; i++) {
            while (!stack.isEmpty() && new_heights[stack.peek()] >= new_heights[i]) {
                int curIndex = stack.pop();
                if (stack.isEmpty()) {
                    res = Math.max(res, new_heights[curIndex] * (i - curIndex));
                } else {
                    int preIndex = stack.peek();
                    res = Math.max(res, new_heights[curIndex] * (i - preIndex - 1));
                }
            }
            stack.add(i);
        }
        return res;
    }
}
